#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <limits>
#include <sstream>

using namespace std;

int GCD(int a, int b){
	if(b == 0)
		return a;
	else if(a < b)
		return GCD(b, a);
	else
		return GCD(b, a%b);
}

#define vItr vector<int>::const_iterator
int VectorInt(vItr start, vItr end){
	vItr mid = start+((end-start)/2);
	if(start == end)
		return 0;
	else
		return (*(mid)%10==0 ? 1 : 0) + VectorInt(start, mid) + VectorInt(mid+1,end);
}

// vItr is defined to vector<int>::iterator
int minVectorInt(vItr start, vItr end){	
	vItr mid = start+((end-start)/2);
	if(start == end)
		return INT_MAX;
	else{
		int midInt = *(mid);
		int left = minVectorInt(start, mid);
		int right = minVectorInt(mid+1,end);
		int lrmin = left < right ? left : right;
		return (midInt < lrmin ? midInt : lrmin);
	}
}

int minVectorInt(const vector<int>& a){
	return minVectorInt(a.begin(), a.end());
}

int SummationSeries(int n){
	if(n == 1)
		return 1;
	else
		return n + SummationSeries(n-1);
}

//problem 1

class trainStopData{
        string stop_id, stop_name;
        double stop_lat, stop_lon;
        public:
        trainStopData(const string& rawData){
                istringstream input(rawData);
                string token;
                getline(input,token,',');
                stop_id = token;
                getline(input,token,',');//junk i dont need
                getline(input,token,',');
                stop_name = token;
                getline(input,token,',');//junk i don't need
                getline(input,token,',');
                stop_lat = atof(token.c_str());
                getline(input,token,',');
                stop_lon = atof(token.c_str());
        }
        friend ostream& operator<<(ostream& os, const trainStopData& tsd);

        string get_id()const{
                return stop_id;
        }
        string get_stop_name()const{
                return stop_name;
        }
        double get_latitude()const{
                return stop_lat;
        }
        double get_longitude()const{
                return stop_lon;
        }
};

ostream& operator<<(ostream& os, const trainStopData& tsd){
        os << tsd.stop_id << " " << tsd.stop_name << " " << tsd.stop_lat << " " << tsd.stop_lon;
        return os;
}

double degrad(double d) {
   return d * M_PI / 180;
}
double haverdist(double lat1, double longit1, double lat2, double longit2)
{
     double r = 6371;
     double dlat = degrad(lat2 - lat1);
     double dlongit = degrad(longit2 - longit1);
     double a = sin(dlat/2)*sin(dlat/2)+
        cos(degrad(lat1))*cos(degrad(lat2))*sin(dlongit/2)*sin(dlongit/2);
     double c = 2*atan2(sqrt(a),sqrt(1-a));
     return r*c;
}

template<class ForwardItr, class UnaryPred>
ForwardItr select_item(ForwardItr start, ForwardItr end, UnaryPred pred){
	ForwardItr tmp_itr = end;
	while(start != end){
		if(pred(*(start)))
			tmp_itr = start;
		start++;
	}
	return tmp_itr;
}

class closest_stop{
public:
	double longitude, latitude, shortest_dist;
	closest_stop(double longitude, double latitude) : longitude(longitude), latitude(latitude), shortest_dist(numeric_limits<double>::max()) {}
	bool operator()(trainStopData stop){
		if(haverdist(latitude, longitude, stop.get_latitude(), stop.get_longitude()) < shortest_dist){
			shortest_dist = haverdist(latitude, longitude, stop.get_latitude(), stop.get_longitude());
			return true;
		}
		else
			return false; 
	}
	
};

int main(){
	cout << GCD(10, 100) << endl;
	int x[6] = {10, 100, 1000, 2, 4, 5};
	vector<int> nums(x, (x+7));
	cout << VectorInt(nums.begin(), nums.end()) << endl;
	cout << minVectorInt(nums) << endl;
	cout << SummationSeries(100) << endl;

	vector<trainStopData> tsd;
	tsd.push_back(trainStopData("103,,238 St,,40.884667,-73.90087,,,1,"));
	tsd.push_back(trainStopData("203,,258 St,,41.884667,-74.90087,,,1,"));
	tsd.push_back(trainStopData("303,,268 St,,42.884667,-75.90087,,,1,"));

	cout << *(select_item(tsd.begin(), tsd.end(), closest_stop(39,-73))) << endl;
	
}
